package com.daybyday.day1.day5;

import com.interview.javabasic.DataStructrue.graph.Graph;
import sun.reflect.generics.tree.Tree;

import java.util.*;

/*
@李子宁
Happy,happy everyday!
冲鸭！
2020/12/3

*/
class TreeNode{
    TreeNode left;
    TreeNode right;
    int node;
    Set<Integer> val;

    public int getNode() {
        return node;
    }

    public void setNode(int node) {
        this.node = node;
    }

    public Set<Integer> getVal() {
        return val;
    }

    public void setVal(Set<Integer> val) {
        this.val = val;
    }

    TreeNode(int a, Set<Integer> x){
        val = x;
        node = a;
    }
}
public class GraphToTree {
    public static void main(String[] args) {
        int[][] graph= {
                {0,2,1,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0},
                {2,0,0,0,1,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0},
                {1,0,0,4,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {0,0,4,0,1,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {0,1,2,1,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {0,0,0,2,4,0,0,4,2,0,0,0,0,0,0,0,0,0,0,0},
                {0,0,0,0,0,0,0,2,0,7,0,0,0,2,0,0,0,0,0,0},
                {0,0,0,0,0,4,2,0,0,0,2,0,0,2,0,0,0,0,0,0},
                {0,0,0,0,0,2,0,0,0,0,0,2,0,0,0,0,0,0,0,0},
                {0,0,0,0,0,0,7,0,0,0,2,0,0,0,0,0,0,0,0,0},
                {0,0,0,0,0,0,0,2,0,2,0,1,0,0,0,0,0,0,0,0},
                {0,0,0,0,0,0,0,0,2,0,1,0,0,0,0,0,0,0,0,0},
                {2,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0},
                {0,2,0,0,0,0,2,2,0,0,0,0,1,0,1,3,0,0,0,0},
                {0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,2,0,0,0,0},
                {0,0,0,0,0,0,0,0,0,0,0,0,0,3,2,0,2,0,0,2},
                {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,2,8,0},
                {0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,2,0,0,0},
                {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,8,0,0,1},
                {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,1,0}
        };

        ArrayList<String> points = new ArrayList<>();
        for (int i = 0; i < graph.length; i++) {
            points.add(i+1+"");
        }
        HashMap<Integer,Integer> gs = new HashMap<>();
        for (int i = 0; i < graph.length; i++) {
            int[] ints = graph[i];
            gs.put(i + 1, getSum(graph[i]));
        }

        HashMap<Integer,Integer> nbSum = new HashMap<>();
        for (int i = 0; i < graph.length; i++) {
            nbSum.put(i + 1, getLaberSum(i+1, graph, gs)) ;
        }
        for (Integer integer : nbSum.keySet()) {
            System.out.print(integer + ":" + nbSum.get(integer) + "  ");
        }

        System.out.println();

        for (Integer integer : gs.keySet()) {
            System.out.print(integer + ":" + gs.get(integer) + "  ");
        }

        ArrayList<Integer> remove = new ArrayList<>();
        TreeNode root = getMinList(graph, gs);
        points.remove(root.node+"");
        remove.add(root.node);
        TreeNode tmp = null;
        Set<Integer> minRoot = getMinRoot(gs,remove,root.val, nbSum, points, graph);
        while (points.size() != 0){
            if( isContainsMinRoot(minRoot,root.val,nbSum) != -1){
                int ins = isContainsMinRoot(minRoot,root.val,nbSum);
                TreeNode newNode = makeNewTmpNode(minRoot,nbSum);
                points.remove(ins+"");
                remove.add(ins);
                minRoot.remove(ins);
                if (tmp == null){
                    newNode.left = root;
                    newNode.right = tmp;
                }else {
                    newNode.left = tmp;
                    newNode.right = root;
                }
                tmp = newNode;
                root = tmp;
                minRoot = getMinRoot(gs,remove,tmp.val,nbSum,points,graph);
            }else{
                int minNode = 0;
                int min = Integer.MAX_VALUE;
                for (Integer integer : minRoot) {
                    if (nbSum.get(integer) < min){
                        min = nbSum.get(integer);
                        minNode = integer;
                    }
                }
                Set<Integer> tmpSet = new HashSet<>();
                tmpSet.add(minNode);
                Set<Integer> minRoot1 = getMinRoot(gs,remove,tmpSet, nbSum, points, graph);
                System.out.println(minRoot1);
                root = makeNewTmpNode(minRoot1,nbSum);
                points.remove(root.node + "");
                remove.add(root.node);
                minRoot.remove(root.node);
                for (Integer integer : root.val) {
                    minRoot.add(integer);
                }

              //  TreeNode tmps = makeNewTmpNode(minRoot,nbSum);
              // minRoot = root.val;
            }

        //Set<Integer> minRoot1 = getMinRoot(root.val, nbSum, points, graph);
        //System.out.println(minRoot1);
        //System.out.println(isContainsMinRoot(minRoot1,root.val,nbSum));
        }
    }

    public static TreeNode makeNewTmpNode(Set<Integer> set,HashMap<Integer,Integer> map){
        int min = Integer.MAX_VALUE;
        int root = 0;
        for (Integer integer : set) {
            if (map.get(integer) < min){
                min = map.get(integer);
                root = integer;
            }
        }
        set.remove(root);
        return new TreeNode(root,set);
    }

    public static int isContainsMinRoot(Set<Integer> set,Set<Integer> root,HashMap<Integer,Integer> map){
        int min = Integer.MAX_VALUE;
        int tmproot = 0;
        for (Integer integer : set) {
            if (map.get(integer) < min){
                min = map.get(integer);
                tmproot = integer;
            }
        }
        return root.contains(tmproot) ? tmproot:-1;
    }

    public static Set<Integer> getMinRoot(HashMap<Integer,Integer> singleMap,ArrayList<Integer> remove,Set<Integer> set,HashMap<Integer,Integer> map,ArrayList<String> list,int[][] graph){
        int min = Integer.MAX_VALUE;
        Set<Integer> res = null;
        for (Integer integer : set) {
            int sum = map.get(integer);
            for (int i = 0; i < graph[integer - 1].length; i++) {
                if ( graph[integer-1][i] != 0 && remove.contains(i + 1)){
                    sum -= singleMap.get(i + 1);
                }
            }
            if (sum < min){
                min = sum;
                res = new HashSet<>(set);
                res.add(integer);
                for (int i = 0; i < graph[integer - 1].length; i++) {
                    if (graph[integer - 1][i] != 0 && list.contains(i + 1 + "")){
                        res.add(i + 1);
                    }
                }
            }
        }
        return res;
    }


    public static int getLaberSum(int i,int[][] graph,HashMap<Integer,Integer> map){
        int res = 0;
        res += map.get(i);
        for (int j = 0; j < graph[i - 1].length; j++) {
            if (graph[i - 1][j] != 0){
                res += map.get(j + 1);
            }
        }
        return res;
    }

    public static int getSum(int[] list){
        int res = 0;
        for (Integer integer : list) {
            res += integer;
        }
        return res;
    }

    public static TreeNode getMinList(int[][] graph,HashMap<Integer,Integer> map){
        int min = Integer.MAX_VALUE;
        int tmp = 0;
        TreeNode res = null;
        int root = 0;
        for (int i = 0; i < graph.length; i++) {
            Set<Integer> list = new HashSet<>();
            tmp = map.get(i + 1);
            root = i + 1;
            for (int j = 0; j < graph[i].length; j++) {
                if (graph[i][j] != 0){
                    list.add(j + 1);
                    tmp += map.get(j + 1);
                    root = map.get(root) > map.get( j + 1)? j + 1:root;
                }
            }
            if (tmp < min){
                res = new TreeNode(root,list);
                min = tmp;
            }
        }
        return res;

    }
}
